Field of the Invention
The present invention is directed in general to error detection and correction techniques used to verify data integrity between two nodes in a communications network. In one aspect, the present invention relates to determining checksums, such as cyclic redundancy check (CRC) codes.
Description of the Related Art
In data processing systems, data communicated from a source node to a destination node should be received accurately. To this end, error detection and correction (or error control) techniques are provided to enable reliable delivery of digital data between nodes. For example, a cyclic redundancy check (CRC) is an error-detecting code commonly used in digital networks and storage devices to detect changes to transmitted blocks of data by using a predetermined algorithm to compute a CRC sum at the transmitting/source node that is appended to data being transmitted. CRC sums are typically a check (data verification) value that is computed as a redundancy (e.g., it expands the message without adding information) using an algorithm based on cyclic codes, such as by computing the remainder of a polynomial division of the data block contents being transmitted. At the receiving/destination node, the received CRC sum can be compared to a similar CRC sum computed from the received data blocks. If the two CRC sums are identical, the transmitted data is presumed correct, but if the generated CRC sums do not match, an error is indicated, possibly along with corrective action against the presumed data corruption.
CRC sums may be computed in different ways with different applications. For example, CRC calculations can be performed in either hardware or software. To implement a CRC calculation in hardware, a dedicated hardware engine is typically provided within the system to perform the CRC calculation by sending the data to be subjected to such a CRC calculation to the hardware engine for calculation of the CRC, which is then appended to the data, e.g., for transmission from the system. Various drawbacks exist to using such an offload engine, including the overhead of sending data to the engine. Furthermore, it is difficult to perform a stateless hardware offload. That is, typically additional state-based overhead data also needs to be transmitted, increasing complexity and slowing the progress of useful work. In other applications. CRC calculations may be performed in software, typically by using lookup table schemes. However, such software calculations of CRC values are notoriously slow, computationally intensive, and memory hogs, impacting cost, degrading network performance, and consuming processing and memory resources to such an extent that software-based CRC calculation may not be suitable for general use in high-speed networks. With both hardware and software solutions, there are challenges with providing an efficient mechanism for recalculating an existing CRC sum when a portion of data within a data block is removed or altered without requiring the recalculation of the CRC sum over the entire data block. As a result, the existing solutions for efficiently and flexibly calculating CRC sums to enable reliable data delivery are extremely difficult at a practical level.